Tại trung tâm của thuật toán bảng băm là một mảng thường được gọi là bảng băm. Thuật toán bảng băm tính ra một chỉ số cho mỗi khóa và dùng chỉ số này để đặt dữ liệu vào mảng. Hàm số thực hiện việc tính toán này gọi là hàm băm, f:

index = f(key, array_size)

Hàm băm tính toán một chỉ số trong mảng từ khóa và kích thước của mảng. Trong hợp ngữ hoặc các ngôn ngữ lập trình bậc thấp khác, một hàm băm có thể tạo ra chỉ số chỉ với một hoặc hai lệnh máy.

Chọn một hàm băm tốt

Hàm băm tốt và thuật toán tốt là hai yếu tố cần thiết để bảng băm hoạt động hiệu quả, nhưng không dễ để đạt được.

Một yêu cầu cơ bản là hàm băm nên phân bố đều các giá trị băm trong mảng. Phân bố không đều làm tăng số lượng va chạm, và do đó tăng chi phí giải quyết chúng. Tính đồng đều đôi khi khó có thể đảm bảo trong thiết kế, nhưng có thể được đánh giá trong thực tiễn bằng cách sử dụng các bài kiểm tra thống kê, ví dụ như, kiểm tra chi-bình phương.

Trong phương pháp địa chỉ mở, các hàm băm cũng nên tránh hiện tượng phân nhóm (ánh xạ hai hay nhiều khóa đến các vị trí liên tiếp trong mảng). Phân nhóm như vậy có thể khiến chi phí tra cứu tăng vọt, ngay cả khi hệ số đầy thấp và va chạm là không thường xuyên.

Các hàm băm mật mã học được cho là hàm băm tốt cho bất kỳ kích thước bảng nào, hoặc bằng cách tính số dư hoặc bằng mặt nạ bit. Tuy nhiên, những phẩm chất này khó có thể bù lại chi phí tính toán lớn hơn nhiều và sự phức tạp của thuật toán.

Hàm băm hoàn hảo.

Nếu tất cả các khóa đều được biết trước khi tạo bảng, có thể sử dụng một hàm băm hoàn hảo để tạo ra một bảng băm hoàn hảo không có va chạm. Nếu sử dụng hàm băm hoàn hảo tối thiểu, thì mọi vị trí trong bảng băm đều được sử dụng.

Hàm băm hoàn hảo cho phép tra cứu trong thời gian hằng số trong trường hợp xấu nhất. Điều này là trái ngược với kết quả cho phương pháp kết nối và phương pháp địa chỉ mở. Hai phương pháp này có thời gian tra cứu trung bình thấp, nhưng có thể rất lớn (tỷ lệ thuận với số lượng khóa) đối với một vài khóa.